/**
 * 
 */
package com.gwcloud.leetcode.hot100;

import com.gwcloud.leetcode.common.datastructure.TreeNode;

/**
 * @ClassName   : Leetcode437 
 * @author      : ganwei 
 * @date        : 2020年5月1日
 * @Description : Leetcode437
 */
public class Leetcode0437 {
	/**
	 * -解题思路，双递归解题
	 */
    public static int pathSum(TreeNode root, int sum) {
    	if(root == null){
    		return 0;
    	}
    	
    	return paths(root,sum)+pathSum(root.left,sum)+pathSum(root.right,sum);
    }
    
    public static int paths(TreeNode root, int sum){
    	if(root == null){
    		return 0;
    	}
    	int res = 0;
    	if(root.val == sum){
    		res += 1;
    	}
    	res += paths(root.left,sum-root.val);
    	res += paths(root.right,sum-root.val);
    	return res;
    }
    
    
    public static void main(String args[]){
    	TreeNode t1 = new TreeNode(10);
    	TreeNode t2 = new TreeNode(5);
    	TreeNode t3 = new TreeNode(-3);
    	t1.left = t2;
    	t1.right = t3;
    	int sum = pathSum(t1,15);
    	System.out.println(sum);
    }
}
